package tree;

import linear.Queue;

public class BinaryTree<Key extends Comparable<Key>, Value> {
    private Node root;
    private int N;


    public void put(Key key, Value value) {
        root = put(root, key, value);
    }

    private Node put(Node x, Key key, Value value) {
        if (x == null) {
            N++;
            return new Node(key, value, null, null);
        }
        int cmp = key.compareTo(x.key);
        if (cmp > 0) {
            x.right = put(x.right, key, value);
        } else if (cmp < 0) {
            x.left = put(x.left, key, value);
        } else {
            x.value = value;
        }
        return x;
    }

    public Value get(Key key) {
        return get(root, key);
    }

    private Value get(Node x, Key key) {
        if (x == null) {
            return null;
        }
        int cmp = key.compareTo(x.key);
        if (cmp == 0) {
            return x.value;
        } else if (cmp > 0) {
            return get(x.right, key);
        } else {
            return get(x.left, key);
        }
    }


    public void delete(Key key) {
        root = delete(root, key);
    }

    private Node delete(Node x, Key key) {
        if (x == null) {
            return null;
        }
        int cmp = key.compareTo(x.key);
        if (cmp > 0) {
            x.right = delete(x.right, key);
        } else if (cmp < 0) {
            x.left = delete(x.left, key);
        } else {

            // 找到了
            // 如果当前只有左节点
            if (x.right == null) {
                N--;
                return x.left;
            }
            if (x.left == null) {
                N--;
                return x.right;
            }
            // 左右都存在 找到右子树最小结点顶替
            Node minNode = x.right;
            while (minNode.left != null) {
                minNode = minNode.left;
            }
            Node n = x.right;
            // 删除右子树的最左(即最小) 结点
            while (n.left != null) {
                if (n.left.left == null) {
                    n.left = null;
                } else {
                    n = n.left;
                }
            }
            // 顶替
            minNode.left = x.left;
            minNode.right = x.right;
            x = minNode;
            N--;

        }
        return x;
    }

    public Key min() {
        return min(root).key;
    }

    private Node min(Node x) {
        if (x.left == null) {
            return x;
        }
        return min(x.left);
    }

    public Key max() {
        return max(root).key;
    }

    private Node max(Node x) {
        if (x.right == null) {
            return x;
        }
        return max(x.right);
    }

    /**
     * 后续遍历
     */
    public Queue<Key> afterErgodic() {
        Queue<Key> keys = new Queue<>();
        afterErgodic(root, keys);
        return keys;
    }

    private void afterErgodic(Node x, Queue<Key> keys) {
        if (x == null) {
            return;
        }
        if (x.left != null) {
            afterErgodic(x.left, keys);
        }
        if (x.right != null) {
            afterErgodic(x.right, keys);
        }
        keys.enqueue(x.key);
    }


    /**
     * 中序比那里
     */
    public Queue<Key> midErgodic() {
        Queue<Key> keys = new Queue<>();
        midErgodic(root, keys);
        return keys;
    }

    public void midErgodic(Node x, Queue<Key> keys) {
        if (x == null) {
            return;
        }
        if (x.left != null) {
            midErgodic(x.left, keys);
        }
        keys.enqueue(x.key);
        if (x.right != null) {
            midErgodic(x.right, keys);
        }
    }


    /**
     * 前序遍历
     */
    public Queue<Key> preErgodic() {
        Queue<Key> keys = new Queue<>();
        preErgodic(root, keys);
        return keys;
    }

    private void preErgodic(Node x, Queue<Key> keys) {
        if (x == null) {
            return;
        }
        // 前序遍历
        // 根
        keys.enqueue(x.key);
        // 左
        if (x.left != null) {
            preErgodic(x.left, keys);
        }
        // 右
        if (x.right != null) {
            preErgodic(x.right, keys);
        }
    }

    public Queue<Key> layerErgodic() {
        Queue<Key> keys = new Queue<>();
        Queue<Node> nodes = new Queue<>();

        nodes.enqueue(root);
        while (!nodes.isEmpty()) {
            Node x = nodes.dequeue();
            if (x.left != null) {
                nodes.enqueue(x.left);
            }
            if (x.right != null) {
                nodes.enqueue(x.right);
            }
            keys.enqueue(x.key);
        }
        return keys;
    }

    private class Node {
        public Key key;
        public Value value;
        public Node left;
        public Node right;

        public Node(Key key, Value value, Node left, Node right) {
            this.key = key;
            this.value = value;
            this.left = left;
            this.right = right;
        }
    }


    public int size() {
        return N;
    }

    public static void main(String[] args) {
        BinaryTree<Integer, String> bt = new BinaryTree<>();
        bt.put(4, "二哈");
        bt.put(1, "张三");
        bt.put(3, "李四");
        bt.put(5, "王五");
        System.out.println(bt.size());
        bt.put(1, "老三");
        System.out.println(bt.get(1));
        System.out.println(bt.size());
        bt.delete(1);
        System.out.println(bt.size());

        System.out.println("键的最小值" + bt.min());
        System.out.println("键的最大值" + bt.max());


        System.out.println("遍历测试");

        BinaryTree<String, String> bt2 = new BinaryTree<>();
        bt2.put("E", "5");
        bt2.put("B", "2");
        bt2.put("G", "7");
        bt2.put("A", "1");
        bt2.put("D", "4");
        bt2.put("F", "6");
        bt2.put("H", "8");
        bt2.put("C", "3");
        System.out.println("前序遍历");
        Queue<String> queue = bt2.preErgodic();
        for (String key : queue) {
            System.out.print(key + "=" + bt2.get(key) + " , ");
        }
        System.out.println();
        System.out.println("中序遍历");
        Queue<String> queue2 = bt2.midErgodic();
        for (String key : queue2) {
            System.out.print(key + "=" + bt2.get(key) + " , ");
        }
        System.out.println();
        System.out.println("后序遍历");
        Queue<String> queue3 = bt2.afterErgodic();
        for (String key : queue3) {
            System.out.print(key + "=" + bt2.get(key) + " , ");
        }
        System.out.println();
        System.out.println("层序遍历");
        Queue<String> queue4 = bt2.layerErgodic();
        for (String key : queue4) {
            System.out.print(key + "=" + bt2.get(key) + " , ");
        }

    }
}
